import json
import time
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False] * len(nums)
        dp[-1] = True
        index = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if index - i <= nums[i]:
                index = i
                dp[index] = True
        
        return dp[0]

class OptimizedSolution:
    """优化版本的解法，用于对比"""
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= len(nums) - 1:
                return True
        return True

def load_test_cases(filename="test_cases.json"):
    """从文件加载测试用例"""
    try:
        with open(filename, 'r', encoding='utf-8') as f:
            return json.load(f)
    except FileNotFoundError:
        print(f"测试用例文件 {filename} 不存在，请先运行 gen.py 生成测试用例")
        return []

def run_single_test(solution, test_case, test_id):
    """运行单个测试用例"""
    nums = test_case["input"]
    description = test_case["description"]
    
    try:
        start_time = time.time()
        result = solution.canJump(nums)
        end_time = time.time()
        
        return {
            "test_id": test_id,
            "description": description,
            "input": nums,
            "result": result,
            "execution_time": end_time - start_time,
            "status": "PASS"
        }
    except Exception as e:
        return {
            "test_id": test_id,
            "description": description,
            "input": nums,
            "result": None,
            "execution_time": 0,
            "status": "ERROR",
            "error": str(e)
        }

def compare_solutions():
    """比较原始解法和优化解法"""
    test_cases = load_test_cases()
    if not test_cases:
        return
    
    solution1 = Solution()
    solution2 = OptimizedSolution()
    
    print("=== 解法比较测试 ===")
    print(f"总测试用例数: {len(test_cases)}")
    
    differences = []
    total_time1 = 0
    total_time2 = 0
    
    for i, test_case in enumerate(test_cases):
        nums = test_case["input"]
        
        # 测试原始解法
        start_time = time.time()
        result1 = solution1.canJump(nums)
        time1 = time.time() - start_time
        total_time1 += time1
        
        # 测试优化解法
        start_time = time.time()
        result2 = solution2.canJump(nums)
        time2 = time.time() - start_time
        total_time2 += time2
        
        # 检查结果是否一致
        if result1 != result2:
            differences.append({
                "test_id": i + 1,
                "input": nums,
                "original_result": result1,
                "optimized_result": result2,
                "description": test_case["description"]
            })
    
    print(f"\n结果差异数量: {len(differences)}")
    if differences:
        print("发现以下差异:")
        for diff in differences:
            print(f"  测试 {diff['test_id']}: {diff['description']}")
            print(f"    输入: {diff['input']}")
            print(f"    原始解法结果: {diff['original_result']}")
            print(f"    优化解法结果: {diff['optimized_result']}")
    else:
        print("✅ 所有测试用例结果一致!")
    
    print(f"\n性能比较:")
    print(f"原始解法总时间: {total_time1:.6f}秒")
    print(f"优化解法总时间: {total_time2:.6f}秒")
    print(f"性能提升: {((total_time1 - total_time2) / total_time1 * 100):.2f}%")

def run_comprehensive_test():
    """运行全面测试"""
    test_cases = load_test_cases()
    if not test_cases:
        return
    
    solution = Solution()
    
    print("=== 全面功能测试 ===")
    print(f"总测试用例数: {len(test_cases)}")
    
    passed = 0
    failed = 0
    errors = 0
    
    print("\n测试结果:")
    print("-" * 80)
    
    for i, test_case in enumerate(test_cases):
        result = run_single_test(solution, test_case, i + 1)
        
        status_symbol = "✅" if result["status"] == "PASS" else "❌"
        
        print(f"{status_symbol} 测试 {result['test_id']:2d}: {result['description']}")
        print(f"   输入: {result['input']}")
        print(f"   结果: {result['result']}")
        print(f"   执行时间: {result['execution_time']:.6f}秒")
        
        if result["status"] == "PASS":
            passed += 1
        elif result["status"] == "ERROR":
            errors += 1
            print(f"   错误: {result['error']}")
        else:
            failed += 1
        
        print()
    
    print("=== 测试汇总 ===")
    print(f"通过: {passed}")
    print(f"失败: {failed}")
    print(f"错误: {errors}")
    print(f"总计: {len(test_cases)}")
    print(f"成功率: {(passed / len(test_cases) * 100):.2f}%")

def manual_test():
    """手动测试特定用例"""
    solution = Solution()
    
    print("=== 手动测试模式 ===")
    print("输入数组 (用空格分隔数字，输入 'quit' 退出):")
    
    while True:
        user_input = input("\n请输入数组: ").strip()
        
        if user_input.lower() == 'quit':
            break
        
        try:
            nums = list(map(int, user_input.split()))
            if not nums:
                print("请输入有效的数组")
                continue
            
            start_time = time.time()
            result = solution.canJump(nums)
            end_time = time.time()
            
            print(f"输入: {nums}")
            print(f"结果: {'能够' if result else '不能'}跳到最后一个位置")
            print(f"执行时间: {end_time - start_time:.6f}秒")
            
        except ValueError:
            print("输入格式错误，请输入数字数组")
        except Exception as e:
            print(f"执行错误: {e}")

def main():
    """主函数"""
    print("跳跃游戏测试程序")
    print("1. 运行全面测试")
    print("2. 比较不同解法")
    print("3. 手动测试")
    print("4. 退出")
    
    while True:
        choice = input("\n请选择操作 (1-4): ").strip()
        
        if choice == '1':
            run_comprehensive_test()
        elif choice == '2':
            compare_solutions()
        elif choice == '3':
            manual_test()
        elif choice == '4':
            print("再见!")
            break
        else:
            print("无效选择，请输入 1-4")

if __name__ == "__main__":
    main()
